package org.aplombh.java.awcing.basic.math.fast;

import java.util.Scanner;

/**
 * 给定 n 组 ai,bi,pi，对于每组数据，求出 abiimodpi 的值。
 * <p>
 * 输入格式
 * 第一行包含整数 n。
 * <p>
 * 接下来 n 行，每行包含三个整数 ai,bi,pi。
 * <p>
 * 输出格式
 * 对于每组数据，输出一个结果，表示 abiimodpi 的值。
 * <p>
 * 每个结果占一行。
 * <p>
 * 数据范围
 * 1≤n≤100000,
 * 1≤ai,bi,pi≤2×109
 * 输入样例：
 * 2
 * 3 2 5
 * 4 3 9
 * 输出样例：
 * 4
 * 1
 */
public class FastModularExponentiation_875 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        FastModularExponentiation fme = new FastModularExponentiation();
        for (int i = 0; i < n; i++) {
            long a = scanner.nextLong();
            long k = scanner.nextLong();
            long p = scanner.nextLong();
            System.out.println(fme.qmi(a, k, p));
        }
    }
}

class FastModularExponentiation {

    /**
     * @return a^k%p
     */
    public long qmi(long a, long k, long p) {
        long res = 1;
        while (k != 0) {
            if ((k & 1) != 0) res = res * a % p;
            k >>= 1;
            a = a * a % p;
        }
        return res;
    }
}
